package lpg;

import java.io.IOException;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.BitSet;
import java.util.List;

class Produce
{
    Produce(Control control)
    {
        this.control    = control;
        this.option     = control.option;
        this.grammar    = control.grammar;
        this.base       = control.base;
        this.dfa        = control.dfa;
    }

    //
    // This procedure computes the set of scopes and for each state, the set
    // of non-terminal symbols that are required as candidates for secondary
    // error recovery.  It also optimizes the NAME map accordingly.
    //
    void processAdvancedMaps()
    {
        //
        // These maps are only needed for error recovery.
        //
        if (!option.errorMaps || !option.table)
            return;

        //
        // TOP, STACK, and INDEX are used for the digraph algorithm
        // in the routines COMPUTE_PRODUCES.
        //
        // The array PRODUCES is used to construct two maps:
        //
        // 1) PRODUCES, a mapping from each non-terminal A to the set of
        // non-terminals C such that:
        //
        //                   A  =>*  x C w
        //
        // 2) RIGHT_MOST_PRODUCES, a mapping from each non-terminal A to
        // the set of non-terminals C such that:
        //
        //                   C =>+ A x   and   x =>* %empty.
        //
        // NOTE: This is really a reverse right-most produces mapping,
        //       since given the above rule, we say that
        //       C right-most produces A.
        //
        //
        directProduces = new BoundedArray<IntArrayList>(grammar.firstNonTerminal(), grammar.lastNonTerminal());
        rightProduces = new BoundedArray<BitSetWithOffset>(grammar.firstNonTerminal(), grammar.lastNonTerminal());
        for (int i = grammar.firstNonTerminal(); i <= grammar.lastNonTerminal(); i++) // Initialize each set in PRODUCES array to Empty set.
        {
            directProduces.set(i, new IntArrayList());
            rightProduces.set(i, new BitSetWithOffset(grammar.numNonterminals + 1, grammar.numTerminals));
        }

        //
        // Note that the elements of rightProduces are automatically set to
        // the empty set when initialized. Also, all the elements of
        // directProduces are set to NULL.
        //
        for (int nt = grammar.firstNonTerminal(); nt <= grammar.lastNonTerminal(); nt++)
        {
            IntArrayList clitems = base.clitems.get(nt);
            for (int k = 0, n = clitems.size(); k < n; k++)
            {
                int itemNo = clitems.get(k);
                int symbol = base.itemTable[itemNo].symbol;
                if (grammar.isNonTerminal(symbol))
                {
                    int i = base.itemTable[itemNo].suffixIndex;
                    if (base.first(i).get(grammar.empty) && !rightProduces.get(symbol).get(nt))
                    {
                        rightProduces.get(symbol).set(nt);
                        directProduces.get(symbol).add(nt);
                    }
                }
            }
        }

        //
        // Complete the construction of the rightProduces map for
        // non-terminals using the digraph algorithm.
        // We make sure that each non-terminal A is not present in its own
        // PRODUCES set since we are interested in the non-reflexive
        // (positive) transitive closure.
        //
        indexOf = new int[grammar.numSymbols + 1];
        Arrays.fill(indexOf, Util.OMEGA);
        for (int nt = grammar.firstNonTerminal(); nt <= grammar.lastNonTerminal(); nt++)
        {
            if (indexOf[nt] == Util.OMEGA)
                computeProduces(rightProduces, nt);
            rightProduces.get(nt).clear(nt); // Not reflexive
        }

        //
        // Construct the minimum subset of the domain of the GOTO map
        // needed for automatic secondary level error recovery.   For each
        // state, we start out with the set of all nonterminals on which
        // there is a transition in that state, and pare it down to a
        // subset S, by removing all nonterminals B in S such that there
        // is a goto-reduce action on B by a single production.  If the
        // READ-REDUCE option is not turned on, then, we check whether or
        // not the goto action on B is to an LR(0) reduce state.Once we have
        // our subset S, we further reduce its size as follows.  For each
        // nonterminal A in S such that there exists another nonterminal
        // B in S, where B != A,  A ->+ Bx  and  x =>* %empty, we remove A
        // from S.
        //
        // Initially, all the elements of the array ntList (which is
        // indexable by the nonterminals) except for the element associated
        // with the "accept" nonterminal are set to OMEGA.
        // At the end of this process, the nonterminal elements whose
        // ntList values are still OMEGA are precisely the nonterminal
        // symbols that will never be used as candidates.
        //
        // Compute the useful[] map.
        //
        assert gdIndex.isEmpty();
        assert gdRange.isEmpty();
        gdIndex.add(0); // There is no state 0
        BitSetWithOffset set = new BitSetWithOffset(grammar.numNonterminals + 1, grammar.numTerminals);
        useful = new BoundedBooleanArray(grammar.numTerminals + 1, grammar.numSymbols);
        for (int stateNo = 1; stateNo <= dfa.numStates; stateNo++)
        {
            IntArrayList ntSet = new IntArrayList();
            assert (gdIndex.size() == stateNo);
            gdIndex.add(gdRange.size());

            set.clear();

            Dfa.GotoHeader goTo = dfa.statset.element(stateNo).goTo;
            for (int i = 0, n = goTo.size(); i < n; i++)
            {
                Dfa.GotoTriplet gotoTriplet = goTo.get(i);
                int symbol = gotoTriplet.symbol();
                int state = gotoTriplet.action();
                int ruleNo;
                if (state < 0)
                    ruleNo = -state;
                else
                {
                    Node q = dfa.statset.element(state).kernelItems;
                    ruleNo = (q.next != null) ? 0 : base.itemTable[q.value].ruleNumber;
                }
                if (ruleNo == 0 || grammar.rhsSize(ruleNo) != 1)
                {
                    ntSet.add(symbol);
                    set.or(rightProduces.get(symbol));
                    useful.set(symbol, true); // mark element "symbol" as useful.
                }
            }

            for (int k = 0, n = ntSet.size(); k < n; k++)
            {
                int symbol = ntSet.get(k);
                if (!set.get(symbol))
                    gdRange.add(symbol);
            }
        }
        assert (gdIndex.size() == dfa.numStates + 1);
        gdIndex.add(gdRange.size()); // add a gate!!!

        if (option.scopes)
            processScopes();
    }

    //
    // This procedure is used to compute the transitive closure of
    // the PRODUCES, LEFT_PRODUCES and rightProduces maps.
    //
    private void computeProduces(BoundedArray<BitSetWithOffset> produces, int symbol)
    {
        stack.add(symbol);
        int index = stack.size();
        indexOf[symbol] = index;

        IntArrayList symbolProduces = directProduces.get(symbol);
        for (int i = 0, n = symbolProduces.size(); i < n; i++)
        {
            int newSymbol = symbolProduces.get(i);
            if (indexOf[newSymbol] == Util.OMEGA)  // first time seen?
                computeProduces(produces, newSymbol);
            indexOf[symbol] = Math.min(indexOf[symbol], indexOf[newSymbol]);
            produces.get(symbol).or(produces.get(newSymbol));
        }

        if (indexOf[symbol] == index)  // symbol is SCC root
        {
            int top = stack.size() - 1;
            for (int newSymbol = stack.remove(top); newSymbol != symbol; newSymbol = stack.remove(--top))
            {
                produces.set(newSymbol, (BitSetWithOffset)produces.get(symbol).clone());
                indexOf[newSymbol] = Util.INFINITY;
            }
            indexOf[symbol] = Util.INFINITY;
        }
    }

    //
    // Compute set of "scopes" and use it to construct SCOPE map.
    //
    private void processScopes()
    {
        //
        // Each element of stateIndex points to the start of a list in scope_state. Element zero of
        // the scope_state array is initialized to 0, indicating a null list. Initially, all elements
        // of stateIndex point to this null list. Later, all reachable nonterminals will be reassigned
        // to their respective list in scope_state. However, if the grammar contains unreachable nonterminals
        // they will not be reassigned to a new list and will instead continue to point to the default null list.
        //
        BoundedIntArray stateIndex =
                new BoundedIntArray(grammar.firstNonTerminal(), grammar.lastNonTerminal());

        BoundedArray<IntArrayList> statesOf =
                new BoundedArray<IntArrayList>(grammar.firstNonTerminal(), grammar.lastNonTerminal());
        for (int i = grammar.firstNonTerminal(); i <= grammar.lastNonTerminal(); i++)
            statesOf.set(i, new IntArrayList());
        int[] prefixIndex = new int[grammar.numItems + 1];
        int[] suffixIndex = new int[grammar.numItems + 1];

        nextItem = new int[grammar.numItems + 1];
        symbolSeen = new BoundedBooleanArray(grammar.firstNonTerminal(), grammar.lastNonTerminal());

        //
        // Make the rightProduces map reflexive.  Recall that
        // rightProduces is a mapping from each nonterminal B into the set
        // of nonterminals A such that:
        //
        //    A =>rm* B
        //
        // Next, initialize and construct the LEFT_PRODUCES map. Initially,
        // all the sets in LEFT_PRODUCES are set to the empty map.
        // LEFT_PRODUCES is a mapping  from each nonterminal A into the set
        // of nonterminals B such that:
        //
        //    A =>lm* B x
        //
        // for some arbitrary string x.
        //
        // Since A ->* A for all A,  we insert A in PRODUCES(A)  (but not
        // in the linked list).
        //
        //
        leftProduces = new BoundedArray<BitSetWithOffset>(grammar.firstNonTerminal(), grammar.lastNonTerminal());
        for (int nt = grammar.firstNonTerminal(); nt <= grammar.lastNonTerminal(); nt++)
        {
            rightProduces.get(nt).set(nt); // make reflexive

            BitSetWithOffset leftProduceSet =
                    new BitSetWithOffset(grammar.numNonterminals + 1, grammar.numTerminals);
            leftProduces.set(nt, leftProduceSet);
            leftProduceSet.set(nt); // reflexive
            IntArrayList directProduce = directProduces.get(nt);
            directProduce.clear(); // reset the list (tuple) to empty

            IntArrayList clitems = base.clitems.get(nt);
            for (int k = 0, n = clitems.size(); k < n; k++)
            {
                for (int itemNo = clitems.get(k), symbol;
                     grammar.isNonTerminal((symbol = base.itemTable[itemNo].symbol));
                     itemNo++)
                {
                    if (!leftProduceSet.get(symbol))
                    {
                        leftProduceSet.set(symbol);
                        directProduce.add(symbol);
                    }
                    if (!base.isNullable(symbol))
                        break;
                }
            }
        }

        //
        // Complete the construction of the LEFT_produces map for
        // non_terminals using the digraph algorithm.
        //
        Arrays.fill(indexOf, Util.OMEGA);
        for (int nt = grammar.firstNonTerminal(); nt <= grammar.lastNonTerminal(); nt++)
            if (indexOf[nt] == Util.OMEGA)
                computeProduces(leftProduces, nt);

        //
        // Allocate and initialize the PRODUCES array to construct the
        // PRODUCES map.  After allocation, CALLOC sets all sets to empty.
        // Since A ->* A for all A,  we insert A in PRODUCES(A)  (but not
        // in the linked list).
        //
        produces = new BoundedArray<BitSetWithOffset>(grammar.firstNonTerminal(), grammar.lastNonTerminal());
        for (int nt = grammar.firstNonTerminal(); nt <= grammar.lastNonTerminal(); nt++)
        {
            BitSetWithOffset ntSet = new BitSetWithOffset(grammar.numNonterminals + 1, grammar.numTerminals);
            produces.set(nt, ntSet);
            ntSet.set(nt); // reflexive
            IntArrayList directProduce = directProduces.get(nt);
            directProduce.clear(); // reset the list (tuple) to empty

            IntArrayList clitems = base.clitems.get(nt);
            for (int k = 0, n = clitems.size(); k < n; k++)
            {
                for (int itemNo = clitems.get(k), symbol;
                     (symbol = base.itemTable[itemNo].symbol) != grammar.empty;
                     itemNo++)
                {
                    if (grammar.isNonTerminal(symbol))
                    {
                        if (!ntSet.get(symbol))
                        {
                            ntSet.set(symbol);
                            directProduce.add(symbol);
                        }
                    }
                }
            }
        }

        //
        // Complete the construction of the PRODUCES map for
        // non_terminals using the digraph algorithm.
        //
        // Since $ACC =>* x A y for all nonterminal A in the grammar, a
        // single call to COMPUTE_PRODUCES does the trick.
        //
        Arrays.fill(indexOf, Util.OMEGA);
        computeProduces(produces, grammar.acceptImage);

        //
        // Construct a mapping from each non_terminal A into the set of
        // items of the form [B . x . A y].
        //
        itemOf = new BoundedIntArray(grammar.firstNonTerminal(), grammar.lastNonTerminal());
        itemOf.fill(Util.NIL);
        for (int itemNo = 1; itemNo <= grammar.numItems; itemNo++)
        {
            int dotSymbol = base.itemTable[itemNo].symbol;
            if (grammar.isNonTerminal(dotSymbol))
            {
                nextItem[itemNo] = itemOf.get(dotSymbol);
                itemOf.set(dotSymbol, itemNo);
            }
        }

        //
        // Construct a list of scoped items in itemList.
        // Scoped items are derived from rules of the form  A.x B y such
        // that B =>* w A z, %empty not in FIRST(y), and it is not the case
        // that x = %empty and B ->* A v.
        // Scoped items may also be identified by the user, using a "recovery"
        // symbol as a marker in a production.
        // As scoped items are added to the list, we keep track of the
        // longest prefix encountered.  This is subsequently used to
        // bucket sort the scoped items in descending order of the length
        // of their prefixes.
        //
        itemList = new int[grammar.numItems + 1];
        Arrays.fill(itemList, Util.OMEGA);
        int itemRoot = Util.NIL;
        int maxPrefixLength = 0;
        StringBuilder tok = new StringBuilder(Control.SYMBOL_SIZE);
        for (int itemNo = 1; itemNo <= grammar.numItems; itemNo++)
        {
            int dotSymbol = base.itemTable[itemNo].symbol;

            //
            // A user-specified recovery item is automatically recognized as a
            // scope. Note that if the item is improper (in that its prefix is
            // nullable, we've already issued a warning for it.
            //
            if (grammar.isRecover(dotSymbol))
            {
                if (!isItemPrefixNullable(itemNo))
                {
                    if (itemList[itemNo] == Util.OMEGA)
                    {
                        itemList[itemNo] = itemRoot;
                        itemRoot = itemNo;
                        maxPrefixLength = Math.max(maxPrefixLength, base.itemTable[itemNo].dot);
                    }
                }
                else
                {
                    grammar.restoreSymbol(tok, grammar.retrieveString(dotSymbol));

                    int ruleNo = base.itemTable[itemNo].ruleNumber;
                    Grammar.RuleElement rule = grammar.rules.get(ruleNo);
                    int errorLocation = control.lexStream.startLocation(rule.firstTokenIndex);
                    InputFileSymbol inputFileSymbol = control.lexStream.getFileSymbol(rule.firstTokenIndex);
                    int errorTokenIndex = control.lexStream.getNextToken(inputFileSymbol, errorLocation);
                    Token currentToken = control.lexStream.getTokenReference(errorTokenIndex);
                    currentToken.setEndLocation(control.lexStream.endLocation(rule.lastTokenIndex));
                    currentToken.setKind(0);

                    option.emitInformative(errorTokenIndex,
                            "This rule is not processed as a scope because the prefix preceding the recovery symbol \"" +
                            tok + "\" is nullable");
                }
            }
            else if (grammar.isNonTerminal(dotSymbol))
            {
                //
                // Check whether or not itemNo is a scope. If so, add it to the
                // itemList of scopes.
                //
                int symbol = grammar.rules.get(base.itemTable[itemNo].ruleNumber).lhs;
                if (!base.first(base.itemTable[itemNo].suffixIndex).get(grammar.empty) &&
                     produces.get(dotSymbol).get(symbol))
                {
                    if (isScope(itemNo))
                    {
                        int i = itemNo + 1;
                        while (true)
                        {
                            symbol = base.itemTable[i].symbol;
                            if (grammar.isTerminal(symbol))
                                break;
                            if (!base.isNullable(symbol))
                                break;
                            i++;
                        }
                        if (grammar.isNonTerminal(symbol))
                        {
                            symbolSeen.fill(false);
                            symbol = getShiftSymbol(symbol);
                        }

                        if (symbol != grammar.empty && itemList[i] == Util.OMEGA)
                        {
                            itemList[i] = itemRoot;
                            itemRoot = i;
                            maxPrefixLength = Math.max(maxPrefixLength, base.itemTable[i].dot);
                        }
                    }
                }
            }
        }

        //
        // In this loop, the prefix and suffix string for each scope in
        // entered into a table.  We also use the symbolSeen array to
        // identify the set of left-hand side symbols associated with the
        // scopes.
        //
        symbolSeen.fill(false);
        int numScopes = 0;
        for (int itemNo = itemRoot; itemNo != Util.NIL; itemNo = itemList[itemNo])
        {
            int ruleNo = base.itemTable[itemNo].ruleNumber;
            int symbol = grammar.rules.get(ruleNo).lhs;
            numScopes++;

            symbolSeen.set(symbol, true);

            prefixIndex[itemNo] = insertPrefix(itemNo);
            suffixIndex[itemNo] = insertSuffix(itemNo);
        }

        //
        // We now construct a mapping from each nonterminal symbol that is
        // the left-hand side of a rule containing scopes into the set of
        // states that has a transition on the nonterminal in question.
        //
        BoundedIntArray ntList = new BoundedIntArray(grammar.firstNonTerminal(), grammar.lastNonTerminal());
        int ntRoot = Util.NIL;
        int numStateSets = 0;
        for (int stateNo = 1; stateNo <= dfa.numStates; stateNo++)
        {
            Dfa.GotoHeader goTo = dfa.statset.element(stateNo).goTo;
            for (int i = 0, n = goTo.size(); i < n; i++)
            {
                int symbol = goTo.get(i).symbol();
                if (symbolSeen.get(symbol))
                {
                    if (statesOf.get(symbol).isEmpty())
                    {
                        ntList.set(symbol, ntRoot);
                        ntRoot = symbol;
                        numStateSets++;
                    }
                    statesOf.get(symbol).add(stateNo);
                }
            }
        }

        //
        // Next, we used the optimal partition procedure to compress the
        // space used by the sets of states, allocate the SCOPE structure
        // and store the compressed sets of states in it.
        // We also sort the list of items by the length of their prefixes in
        // descending order.  This is done primarily as an optimization.
        // If a longer prefix matches prior to a shorter one, the parsing
        // will terminate quicker.
        //
        // process_scope_states:
        //
        {
            BitSetElement[] collection = new BitSetElement[numStateSets + 1];
            for (int i = 1; i <= numStateSets; i++)
                collection[i] = new BitSetElement(dfa.numStates + 1, i);

            int[] list = new int[numStateSets + 1];
            int[] orderedSymbol = new int[numStateSets + 1];
            for (int symbol = ntRoot, j = 1;
                 symbol != Util.NIL; symbol = ntList.get(symbol), j++)
            {
                list[j] = j;
                orderedSymbol[j] = symbol;
                IntArrayList states = statesOf.get(symbol);
                for (int k = 0, m = states.size(); k < m; k++)
                {
                    collection[j].size++;
                    collection[j].bitSet.set(states.get(k));
                }
            }

            int[] start = new int[numStateSets + 2];
            int[] stack = new int[numStateSets + 1];
            Partition.partset(collection, list, start, stack, dfa.numStates);

            for (int i = 1; i <= numStateSets; i++)
                stateIndex.set(orderedSymbol[i], Math.abs(start[i]));

            scopeState = new int[numStateSets == 0 ? 1 : start[numStateSets + 1]];
            scopeState[0] = 0;
            int[] stateList = new int[dfa.numStates + 1];
            Arrays.fill(stateList, Util.OMEGA);
            for (int i = 1, k = 0; i <= numStateSets; i++)
            {
                if (start[i] > 0)
                {
                    int stateRoot = 0;
                    stateList[stateRoot] = Util.NIL;
                    int j = i;
                    for (boolean endNode = (j == Util.NIL);
                         !endNode; endNode = (j == i))
                    {
                        j = stack[j];
                        int symbol = orderedSymbol[j];
                        IntArrayList statesList = statesOf.get(symbol);
                        for (int l = 0, m = statesList.size(); l < m; l++)
                        {
                            int stateNo = statesList.get(l);
                            if (stateList[stateNo] == Util.OMEGA)
                            {
                                stateList[stateNo] = stateRoot;
                                stateRoot = stateNo;
                            }
                        }
                    }

                    for (int stateNo = stateRoot;
                         stateNo != Util.NIL; stateNo = stateRoot)
                    {
                        stateRoot = stateList[stateNo];
                        stateList[stateNo] = Util.OMEGA;
                        scopeState[++k] = stateNo;
                    }
                }
            }

            //
            // Use the BUCKET array as a base to partition the scoped items
            // based on the length of their prefixes.  The list of items in each
            // bucket is kept in the nextItem array sorted in descending order
            // of the length of the right-hand side of the item.
            // Items are kept sorted in that fashion because when two items have
            // the same prefix, we want the one with the shortest suffix to be
            // chosen. In other words, if we have two scoped items, say:
            //
            //    A ::= x . y       and      B ::= x . z     where |y| < |z|
            //
            // and both of them are applicable in a given context with similar
            // result, then we always want A ::= x . y to be used.
            //
            int[] bucket = new int[maxPrefixLength + 1];
            Arrays.fill(bucket, Util.NIL);
            for (int itemNo = itemRoot; itemNo != Util.NIL; itemNo = itemList[itemNo])
            {
                int tail = Util.NIL;

                int k = base.itemTable[itemNo].dot;
                int i = bucket[k];
                for (; i != Util.NIL; tail = i, i = nextItem[i])
                {
                    if (grammar.rhsSize(base.itemTable[itemNo].ruleNumber) >=
                        grammar.rhsSize(base.itemTable[i].ruleNumber))
                       break;
                }

                nextItem[itemNo] = i;
                if (i == bucket[k])
                    bucket[k] = itemNo;         // insert at the beginning
                else
                    nextItem[tail] = itemNo;    // insert in middle or end
            }

            //
            // Reconstruct list of scoped items in sorted order. Since we want
            // the items in descending order, we start with the smallest bucket
            // proceeding to the largest one and insert the items from each
            // bucket in LIFO order in itemList.
            //
            itemRoot = Util.NIL;
            for (int k = 1; k <= maxPrefixLength; k++)
            {
                for (int itemNo = bucket[k]; itemNo != Util.NIL; itemNo = nextItem[itemNo])
                {
                    itemList[itemNo] = itemRoot;
                    itemRoot = itemNo;
                }
            }
        } // End PROCESS_SCOPE_STATES

        //
        // Next, we initialize the remaining fields of the SCOPE structure.
        //
        scopePrefix = new int[numScopes];
        scopeSuffix = new int[numScopes];
        scopeLhsSymbol = new int[numScopes];
        scopeLookAhead = new int[numScopes];
        scopeStateSet = new int[numScopes];

        for (int i = 0, itemNo = itemRoot; itemNo != Util.NIL; i++, itemNo = itemList[itemNo])
        {
            scopePrefix[i] = prefixIndex[itemNo];
            scopeSuffix[i] = suffixIndex[itemNo];
            int ruleNo = base.itemTable[itemNo].ruleNumber;
            Grammar.RuleElement rule = grammar.rules.get(ruleNo);
            scopeLhsSymbol[i] = rule.lhs;
            int symbol = grammar.rhsSym.get(rule.rhsIndex + base.itemTable[itemNo].dot);
            if (grammar.isTerminal(symbol))
                scopeLookAhead[i] = symbol;
            else
            {
                symbolSeen.fill(false);
                scopeLookAhead[i] = getShiftSymbol(symbol);
            }
            scopeStateSet[i] = stateIndex.get(scopeLhsSymbol[i]);
        }

        int scopeElementNum = scopeElement.size();
        scopeRightSide = new int[scopeElementNum == 0
                                     ? 1
                                     : scopeElement.element(scopeElementNum - 1).index +
                                       scopeElement.element(scopeElementNum - 1).size];
        scopeRightSide[0] = 0;
        int scopeIndex = 1;
        for (int j = 0; j < scopeElementNum; j++)
        {
            ScopeElement element = scopeElement.element(j);
            assert(scopeIndex == element.index);

            if (element.item < 0)
            {
                int itemNo = -element.item;
                int ruleNo = base.itemTable[itemNo].ruleNumber;
                for (int index = grammar.rules.get(ruleNo).rhsIndex,
                         k = index + base.itemTable[itemNo].dot - 1;
                         k >= index; // symbols before dot
                         k--)
                    scopeRightSide[scopeIndex++] = grammar.rhsSym.get(k);
            }
            else
            {
                int itemNo = element.item;
                int ruleNo = base.itemTable[itemNo].ruleNumber;
                for (int k = grammar.rules.get(ruleNo).rhsIndex + base.itemTable[itemNo].dot,
                         nextRhsIndex = grammar.rules.get(ruleNo + 1).rhsIndex;
                         k < nextRhsIndex; // symbols after dot
                         k++)
                    scopeRightSide[scopeIndex++] = grammar.rhsSym.get(k);
            }
            scopeRightSide[scopeIndex++] = 0;
        }
    }

    //
    // Given an item of the form [A . w B x]. This function
    // computes whether or not the prefix w is nullable.
    //
    private boolean isItemPrefixNullable(int itemNo)
    {
        for (int i = itemNo - base.itemTable[itemNo].dot; i < itemNo; i++)
        {
            int symbol = base.itemTable[i].symbol;
            if (grammar.isTerminal(symbol))
                return false;
            if (!base.isNullable(symbol))
                return false;
        }
        return true;
    }

    //
    // This procedure checks whether or not an item [A . w B x] is a
    // valid scope. The item in question is known to satisfy the following
    // conditions:
    //     . B ->* y A z
    //     . it is not the case that x =>* %empty
    //
    // Such an item is a valid scope if, in addition, it satisfies  the
    // following conditions:
    //
    // 1) either it is not the case that w =>* %empty or it is not the
    //    case that B =>lm* A.
    // 2) it is not the case that whenever A is introduced through
    //    closure, it is introduced by a nonterminal C where C =>rm* A
    //    and C =>rm+ B.
    //
    private boolean isScope(int itemNo)
    {
        //
        // If the prefix of itemNo is not nullable
        //
        if (!isItemPrefixNullable(itemNo))
            return true;

        int lhsSymbol = grammar.rules.get(base.itemTable[itemNo].ruleNumber).lhs;
        int target = base.itemTable[itemNo].symbol;
        if (leftProduces.get(target).get(lhsSymbol))
            return false;

        if (base.itemTable[itemNo].dot > 0)
            return true;

        symbolSeen.fill(false);

        return scopeCheck(lhsSymbol, target, lhsSymbol);
    }

    //
    // Given a nonterminal lhsSymbol and a nonterminal TARGET where,
    //
    //                     lhsSymbol .= TARGET x
    //
    // find out if whenever lhsSymbol is introduced through closure, it
    // is introduced by a nonterminal SOURCE such that
    //
    //                     SOURCE ->rm* lhsSymbol
    //
    //                               and
    //
    //                     SOURCE ->rm+ TARGET
    //
    private boolean scopeCheck(int lhsSymbol, int target, int source)
    {
        symbolSeen.set(source, true);

        if (rightProduces.get(target).get(source) && rightProduces.get(lhsSymbol).get(source))
            return false;

        for (int itemNo = itemOf.get(source); itemNo != Util.NIL; itemNo = nextItem[itemNo])
        {
            if (base.itemTable[itemNo].dot != 0)
                return true;

            int ruleNo = base.itemTable[itemNo].ruleNumber;
            int symbol = grammar.rules.get(ruleNo).lhs;
            if (!symbolSeen.get(symbol))        // not yet processed
            {
                if (scopeCheck(lhsSymbol, target, symbol))
                    return true;
            }
        }

        return false;
    }

    //
    // This procedure takes as argument an item and inserts the string
    // prefix of the item preceeding the "dot" into the scope table, if
    // that string is not already there.  In any case, the index  number
    // associated with the prefix in question is returned.
    // NOTE that since both prefixes and suffixes are entered in the
    // table, the prefix of a given item, itemNo, is encoded as
    // -itemNo, whereas the suffix of that item is encoded as +itemNo.
    //
    private int insertPrefix(int itemNo)
    {
        return insertScope(-itemNo);
    }

    //
    // This procedure is analoguous to INSERT_PREFIX.  It takes as
    // argument an item, and inserts the suffix string following the dot
    // in the item into the scope table, if it is not already there.
    // In any case, it returns the index associated with the suffix.
    // When inserting a suffix into the table, all nullable nonterminals
    // in the suffix are disregarded.
    //
    private int insertSuffix(int itemNo)
    {
        return insertScope(itemNo);
    }

    private int insertScope(int itemNo)
    {
        ScopeElement scope = new ScopeElement(
                itemNo, scopeElement.size(), grammar, base, scopeElement);
        scope = scopeElement.findOrInsert(scope);
        if (!scope.isCompleted())
            scope.complete();

        return scope.index;
    }

    //
    // This procedure is similar to the global procedure PrintItem.
    //
    void processScopesOutput()
    {
        if (!option.list)
            return;

        StringBuilder line = new StringBuilder(Control.PRINT_LINE_SIZE);
        StringBuilder tok = new StringBuilder(Control.SYMBOL_SIZE);
        StringBuilder tmp = new StringBuilder(Control.PRINT_LINE_SIZE);

        control.printHeading();
        try
        {
            option.syslis.write(Util.LINE_SEPARATOR);
            option.syslis.write("Scopes:");
            option.syslis.write(Util.LINE_SEPARATOR);

            for (int k = 0; k < scopeLhsSymbol.length; k++)
            {
                int symbol = scopeLhsSymbol[k];
                grammar.restoreSymbol(tok, grammar.retrieveString(symbol));
                int len = Control.PRINT_LINE_SIZE - 5;
                grammar.printLargeToken(line, tok, "", len);
                line.append(" .= ");
                int i = (Control.PRINT_LINE_SIZE / 2) - 1;
                int offset = Math.min(line.length() - 1, i);
                len = Control.PRINT_LINE_SIZE - (offset + 4);

                // locate end of list
                for (i = scopePrefix[k]; scopeRightSide[i] != 0; i++)
                    ;

                for (i = i - 1; i >= scopePrefix[k]; i--) // symbols before dot
                {
                    symbol = scopeRightSide[i];
                    grammar.restoreSymbol(tok, grammar.retrieveString(symbol));
                    if (line.length() + tok.length() > Control.PRINT_LINE_SIZE - 4)
                    {
                        option.syslis.write(Util.LINE_SEPARATOR);
                        option.syslis.write(new String(line));
                        line.delete(0, line.length());
                        Util.fillIn(tmp, offset, ' ');
                        grammar.printLargeToken(line, tok, tmp, len);
                    }
                    else
                        line.append(tok);
                    line.append(' ');
                }

                //
                // We now add a dot "." to the output line, and print the remaining
                // symbols in the right hand side.
                //
                line.append(" .");
                len = Control.PRINT_LINE_SIZE - (offset + 1);

                for (i = scopeSuffix[k]; scopeRightSide[i] != 0; i++)
                {
                    symbol = scopeRightSide[i];
                    grammar.restoreSymbol(tok, grammar.retrieveString(symbol));
                    if (line.length() + tok.length() > Control.PRINT_LINE_SIZE - 1)
                    {
                        option.syslis.write(Util.LINE_SEPARATOR);
                        option.syslis.write(new String(line));
                        line.delete(0, line.length());
                        Util.fillIn(tmp, offset, ' ');
                        grammar.printLargeToken(line, tok, tmp, len);
                    }
                    else
                        line.append(tok);
                    line.append(' ');
                }
                option.syslis.write(Util.LINE_SEPARATOR);
                option.syslis.write(new String(line));
                line.delete(0, line.length());
            }
        }
        catch (IOException e)
        {
        }
    }

    //
    // This procedure takes as parameter a nonterminal, lhsSymbol, and
    // determines whether or not there is a terminal symbol t such that
    // lhsSymbol can rightmost produce a string tX.  If so, t is
    // returned, otherwise EMPTY is returned.
    //
    private int getShiftSymbol(int lhsSymbol)
    {
        if (!symbolSeen.get(lhsSymbol))
        {
            symbolSeen.set(lhsSymbol, true);

            IntArrayList clitems = base.clitems.get(lhsSymbol);
            for (int k = 0, m = clitems.size(); k < m; k++)
            {
                int itemNo = clitems.get(k);
                int ruleNo = base.itemTable[itemNo].ruleNumber;
                if (grammar.rhsSize(ruleNo) > 0)
                {
                    int symbol = grammar.rhsSym.get(grammar.rules.get(ruleNo).rhsIndex);
                    if (grammar.isTerminal(symbol))
                        return symbol;
                    symbol = getShiftSymbol(symbol);
                    if (symbol != grammar.empty)
                        return symbol;
                }
            }
        }

        return grammar.empty;
    }

    boolean isUseful(int nt)
    {
        return useful.get(nt);
    }

    //
    //  The variables below are global counters.
    //
    int numErrorRules = 0;

    final IntArrayList gdIndex = new IntArrayList();
    final IntArrayList gdRange = new IntArrayList();

    int[] scopePrefix = null;
    int[] scopeSuffix = null;
    int[] scopeLhsSymbol = null;
    int[] scopeLookAhead = null;
    int[] scopeStateSet = null;

    int[] scopeRightSide = null;
    int[] scopeState = null;

    private final IntArrayList stack = new IntArrayList();
    private int[] indexOf = null;
    private int[] itemList = null;
    private int[] nextItem = null;
    private int scopeTop = 0;

    private LookupSet<ScopeElement> scopeElement = new LookupSet<ScopeElement>();

    private BoundedIntArray itemOf = null;
    private BoundedBooleanArray symbolSeen = null;
    private BoundedArray<IntArrayList> directProduces = null;
    private BoundedArray<BitSetWithOffset> produces = null;
    private BoundedArray<BitSetWithOffset> rightProduces = null;
    private BoundedArray<BitSetWithOffset> leftProduces = null;
    private BoundedBooleanArray useful = null;

    private final Control control;
    private final Option option;
    private final Grammar grammar;
    private final Base base;
    private final Dfa dfa;

    private static class ScopeElement
    {
        ScopeElement(int item, int scopeIndex,
                Grammar grammar, Base base, LookupSet<ScopeElement> scopeElement)
        {
            this.item           = item;
            this.scopeIndex     = scopeIndex;
            this.grammar        = grammar;
            this.base           = base;
            this.scopeElement   = scopeElement;
        }

        boolean isCompleted()
        {
            return index != 0;
        }

        void complete()
        {
            index = (scopeIndex == 0)
                        ? 1
                        : scopeElement.element(scopeIndex - 1).index +
                          scopeElement.element(scopeIndex - 1).size;
            if (item < 0) // A prefix
                size = base.itemTable[-item].dot + 1;
            else // A suffix
            {
                int ruleNo = base.itemTable[item].ruleNumber;
                size = grammar.rules.get(ruleNo + 1).rhsIndex - grammar.rules.get(ruleNo).rhsIndex
                       - base.itemTable[item].dot + 1;
            }
        }

        public boolean equals(Object obj)
        {
            if (obj == this)
                return true;
            if (!(obj instanceof ScopeElement))
                return false;

            return compare((ScopeElement)obj);
        }

        private boolean compare(ScopeElement scopeElement)
        {
            if ((item ^ scopeElement.item) < 0)
                return false;

            if (item < 0)
            {
                int itemNo1 = -item;
                int itemNo2 = -scopeElement.item;
                if (base.itemTable[itemNo1].dot != base.itemTable[itemNo2].dot)
                    return false;

                for (int i = grammar.rules.get(base.itemTable[itemNo2].ruleNumber).rhsIndex,
                         dot = i + base.itemTable[itemNo2].dot,
                         j = grammar.rules.get(base.itemTable[itemNo1].ruleNumber).rhsIndex;
                     i < dot;
                     i++, j++) // symbols before dot
                {
                    if (grammar.rhsSym.get(i) != grammar.rhsSym.get(j))
                        return false;
                }
            }
            else
            {
                int itemNo1 = item;
                int itemNo2 = scopeElement.item;
                int ruleNo1 = base.itemTable[itemNo1].ruleNumber;
                int ruleNo2 = base.itemTable[itemNo2].ruleNumber;
                for (int i = grammar.rules.get(ruleNo1).rhsIndex + base.itemTable[itemNo1].dot,
                         dot1 = grammar.rules.get(ruleNo1 + 1).rhsIndex,
                         j = grammar.rules.get(ruleNo2).rhsIndex + base.itemTable[itemNo2].dot,
                         dot2 = grammar.rules.get(ruleNo2 + 1).rhsIndex;
                     i < dot1 && j < dot2;
                     i++, j++)
                {
                    if (grammar.rhsSym.get(i) != grammar.rhsSym.get(j))
                        return false;
                }

            }
            return true;
        }

        public int hashCode()
        {
            int result = 1;
            if (item < 0) // A prefix
            {
                int itemNo = -item;
                int ruleNo = base.itemTable[itemNo].ruleNumber;
                for (int i = grammar.rules.get(ruleNo).rhsIndex,    // symbols before dot
                         dotIndex = i + base.itemTable[itemNo].dot;
                     i < dotIndex;
                     i++)
                {
                    result = 31 * result + grammar.rhsSym.get(i);
                }
                return (result << 1) | 1;
            }
            else // A suffix
            {
                int ruleNo = base.itemTable[item].ruleNumber;
                for (int i = grammar.rules.get(ruleNo).rhsIndex + base.itemTable[item].dot,
                         nextRhsIndex = grammar.rules.get(ruleNo + 1).rhsIndex;
                     i < nextRhsIndex; // symbols after dot
                     i++)
                {
                    result = 31 * result + grammar.rhsSym.get(i);
                }
                return result << 1;
            }
        }

        final int item;
        int index = 0;
        int size = 0;
        final int scopeIndex;

        final Grammar grammar;
        final Base base;
        final LookupSet<ScopeElement> scopeElement;
    }

}
